#include "Stack.h"
#include <iostream>
#include<sstream>
#include "CStack.h"
#include "Queue.h"

using namespace std;

string int_to_string(int port) {
	stringstream ss;
	ss << port;
	return ss.str();
}

void decToBinary(int number) {
	Stack st;
	while (number > 0) {
		int m = number % 2;
		st.push(m);
		number = number / 2;
	}

	cout << "size: " << st.size << endl;
	int temp = 0;
	while (st.size > 0) {
		st.pop(temp);
		//rs = rs + temp * pow(10, st.size);
		cout << temp;
	}

}

/*
 * Using stack to parse an simply expression
 */

bool parseBrackets(string input) {
	Stack stack;
	int i = 0;
	while (i < (int) input.length()) {
		char c = input[i++];
		if (c == '(')
			stack.push(1);
		else if (c == '[')
			stack.push(2);
		else if (c == ')') {
			if (stack.size == 0)
				return false;
			else {
				int topST = 0;
				stack.pop(topST);
				if (topST > 1)
					return false;
			}
		} else if (c == ']') {
			int topST = 0;
			stack.pop(topST);
			if (topST < 2)
				return false;
		}
	}

	if (stack.size != 0)
		return false;
	return true;
}

/**
 * Using Stack to convert infix to postfix
 */

bool isOperator(char opt) {
	if (opt == '+' || opt == '-' || opt == '*' || opt == '/')
		return true;
	return false;
}

bool isBrackets(char bracket) {
	if (bracket == '(' || bracket == ')')
		return true;
	return false;
}

int degree(char op) {
	if (op == '+' || op == '-')
		return 1;
	else if (op == '*' || op == '/')
		return 2;
	else if (op == '(' || op == ')')
		return 0;
	return -1;
}

string infixToPostfix(string input) {
	string output;
	CStack stack;
	char topST = '#';
	char aChar = '$';

	for (int i = 0; i < (int) input.length(); i++) {
		aChar = input[i];
		if (!isOperator(aChar) && !isBrackets(aChar))
			output += aChar;
		else {
			if (isOperator(aChar)) {
				if (stack.size == 0)
					stack.push(aChar);
				else {
					if (degree(aChar) > degree(stack.top()))
						stack.push(aChar);
					else {
						while ((degree(aChar) <= degree(stack.top()))
								&& stack.size != 0) {
							stack.pop(topST);
							output += topST;
						}
						stack.push(aChar);
					}
				}
			} else if (isBrackets(aChar)) {
				if (aChar == '(')
					stack.push(aChar);
				else {
					while (stack.top() != '(') {
						stack.pop(topST);
						output += topST;
					}
					stack.pop(topST);
				}
			} else {
				if (aChar == ' ')
					continue;
			}
		}
	}

	while (stack.size != 0) {
		stack.pop(topST);
		output += topST;
	}
	return output;
}

int main() {
	/*
	 int num = 0;
	 cout << "Enter : ";
	 cin >> num;
	 decToBinary(num);*/
//he();
//sortQueue();
	/*string in = "1+3*(2+5)()[]";
	 bool b = parseBrackets(in);
	 cout << "b: " << b;
	 cout << endl;*/

	/*string input = "a+b*c-e*(d-f)";
	 string output = "";
	 output = infixToPostfix(input);
	 cout << "Input : " << input << endl;
	 cout << "Output: " << output << endl;
	 */
	string input = "a+b*c-(d*e/f)*g";
	string output = infixToPostfix(input);
	cout << "In : " << input << endl;
	cout << "Out : " << output << endl;
	return 0;
}

/*
 *
 *
 *
 *
 *
 */
